package DynamicProgramming.Medium;

public class LC0714 {
    /**
     * 官方题解。dp[i,0]表示第i天收盘后，不持有股票时的最大收益；dp[i,1]表示持有股票时的最大收益。
     */
    public static int maxProfit(int[] prices, int fee) {
        int n = prices.length;
        int[][] dp = new int[n + 1][2];
        dp[1][0] = 0;
        dp[1][1] = -prices[0];
        for (int i = 2; i <= n; i++) {
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] - fee + prices[i - 1]);
            dp[i][1] = Math.max(dp[i - 1][0] - prices[i - 1], dp[i - 1][1]);
        }

        return Math.max(dp[n][0], dp[n][1]);
    }

    public static void main(String[] args) {
        int[] prices = new int[]{1, 3, 2, 8, 4, 9};
        System.out.println(maxProfit(prices, 2));
    }
}
